#include "UnionFind1.h"
#include "UnionFind2.h"
#include "UnionFind3.h"
#include "UnionFind4.h"
#include "UnionFind5.h"
#include "UnionFind6.h"
#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

template<typename T>
void Test(int n)
{
	srand(time(NULL));
	T uf(n);

	time_t begin = clock();

	for (size_t i = 0; i < n; i++)
	{
		int p = rand() % n;
		int q = rand() % n;
		uf.Union(p, q);
	}
	
	for (size_t i = 0; i < n; i++)
	{
		int p = rand() % n;
		int q = rand() % n;
		uf.IsConnected(p, q);
	}

	time_t end = clock();

	cout << typeid(T).name() << ", " << 2 * n << " ops, " << double(end - begin) / CLOCKS_PER_SEC << endl;
}

int main()
{
	int n = 200000;
	Test<UF1::UnionFind>(10000);
	Test<UF2::UnionFind>(200000);
	Test<UF3::UnionFind>(200000);
	Test<UF4::UnionFind>(200000);
	Test<UF5::UnionFind>(200000);
	Test<UF6::UnionFind>(200000);

	return 0;
}